// 前几天看了一份鹅场的面试题，算法部分大半是动态规划，最后一题就是写一个计算编辑距离的函数，今天就专门写一篇文章来探讨一下这个问题。
// 我个人很喜欢编辑距离这个问题，因为它看起来十分困难，解法却出奇得简单漂亮，而且它是少有的比较实用的算法（是的，我承认很多算法问题都不太实用）。下面先来看下题目：
//给定字符串s1和s2，计算出将s1转换成s2所有使用的最少的操作
// 你可以对字符串做 插入一个字符串 删除一个字符串 替换一个字符串
// 示例 s1 = "horse" s2 = "ros

// 为什么说这个问题难呢，因为显而易见，它就是难，让人手足无措，望而生畏。
// 为什么说它实用呢，因为前几天我就在日常生活中用到了这个算法。之前有一篇公众号文章由于疏忽，写错位了一段内容，我决定修改这部分内容让逻辑通顺。但是公众号文章最多只能修改 20 个字，且只支持增、删、替换操作（跟编辑距离问题一模一样），于是我就用算法求出了一个最优方案，只用了 16 步就完成了修改。
// 再比如高大上一点的应用，DNA 序列是由 A,G,C,T 组成的序列，可以类比成字符串。编辑距离可以衡量两个 DNA 序列的相似度，编辑距离越小，说明这两段 DNA 越相似，说不定这俩 DNA 的主人是远古近亲啥的。
// 下面言归正传，详细讲解一下编辑距离该怎么算，相信本文会让你有收获。"

// 一、思路
// 编辑距离问题就是给我们两个字符串 s1 和 s2，只能用三种操作，让我们把 s1 变成 s2，求最少的操作数。需要明确的是，不管是把 s1 变成 s2 还是反过来，结果都是一样的，所以后文就以 s1 变成 s2 举例。
// 前文「最长公共子序列」说过，解决两个字符串的动态规划问题，一般都是用两个指针 i,j 分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。

// if s1[i] == s2[j]:
//     啥都别做（skip）
//     i, j 同时向前移动
// else:
//     三选一：
//         插入（insert）
//         删除（delete）
//         替换（replace）

// 有这个框架，问题就已经解决了。读者也许会问，这个「三选一」到底该怎么选择呢？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁。这里需要递归技巧，理解需要点技巧，先看下代码：
const minDistance = (s1: string, s2: string): number => {
  function dp(i: number, j: number): number {
    // # base case
    if (i == -1) return j + 1
    if (j == -1) return i + 1

    if (s1[i] == s2[j]) {
      return dp(i - 1, j - 1) //# 啥都不做
    } else {
      return Math.min(
        dp(i, j - 1) + 1,   // # 插入
        dp(i - 1, j) + 1,    //# 删除
        dp(i - 1, j - 1) + 1 //# 替换
      )
    }
  }
  // # i，j 初始化指向最后一个索引
  return dp(s1.length - 1, s2.length - 1)
}

console.log(minDistance('intention', 'execution'))

// 三、动态规划优化
// 对于重叠子问题呢，前文「动态规划详解」详细介绍过，优化方法无非是备忘录或者 DP table。
// 备忘录很好加，原来的代码稍加修改即可：
// const minDistance2 = (s1: string, s2: string): number => {
//   const memo = {}
//   function dp(i: number, j: number): number {
//     if ((i, j) in memo) {
//       return memo[(i, j)]
//     }

//     if (s1[i] == s2[j]) {
//       memo[(i, j)] = '...'
//     } else {
//       memo[(i, j)] = '...'
//     }
//     return memo[(i, j)]

//   }
//   return dp(s1.length - 1, s2.length - 1)
// }

// 有了之前递归解法的铺垫，应该很容易理解。dp[..][0] 和 dp[0][..] 对应 base case，dp[i][j] 的含义和之前的 dp 函数类似：
// def dp(i, j) -> int
// # 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离

// dp[i-1][j-1]
// # 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离

//dp 函数的 base case 是 i,j 等于 -1，而数组索引至少是 0，所以 dp 数组会偏移一位。
// 既然 dp 数组和递归 dp 函数含义一样，也就可以直接套用之前的思路写代码，唯一不同的是，DP table 是自底向上求解，递归解法是自顶向下求解：

const minDistance2 = (s1: string, s2: string) => {
  let m = s1.length, n = s2.length;
  let dp: number[][] = [[]];
  // base case 
  for (let i = 1; i <= m; i++) {
    dp[i][0] = i;
  }

  for (let j = 1; j <= n; j++) {
    dp[0][j] = j;
  }

  // 自底向上求解
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = min(
          dp[i - 1][j] + 1,
          dp[i][j - 1] + 1,
          dp[i - 1][j - 1] + 1
        );
      }
    }
  }
  // 储存着整个 s1 和 s2 的最小编辑距离
  return dp[m][n];
}

const min = (a: number, b: number, c: number) => {
  return Math.min(a, Math.min(b, c));
}